#include <stdint.h>
#include "mybitmap.h"

// 磁盘相关
#define MYBTREE_DISK_NODE_SIZE 16384
#define MYBTREE_DISK_RECORD_SIZE 256
#define MYBTREE_DISK_FSBLOCK_SIZE 4096
#define MYBTREE_DISK_OFFSET(idx) ((idx) * MYBTREE_DISK_NODE_SIZE)
#define MYBTREE_DISK_DATA_OFFSET(idx) ((idx) * MYBTREE_DISK_RECORD_SIZE)
#define MYBTREE_DISK_INDEX_FILE_SUFFIX ".idx"
#define MYBTREE_DISK_DATA_FILE_SUFFIX ".data"

#define MYBTREE_KEYS_THRETHOD 1023
#define MYBTREE_KEYS_NUM_MAX (MYBTREE_KEYS_THRETHOD * 2 - 1)
#define MYBTREE_KEYS_NUM_MIN (MYBTREE_KEYS_THRETHOD - 1)
#define MYBTREE_CHILDS_NUM_MAX (MYBTREE_KEYS_NUM_MAX + 1)
#define MYBTREE_CHILDS_NUM_MIN (MYBTREE_KEYS_NUM_MIN + 1)
#define MYBTREE_BITMAP_SIZE (1024 * 4 * 10)
#define MYBTREE_NODE_IS_FULL(n) (n->keys_num == MYBTREE_KEYS_NUM_MAX)
#define MYBTREE_NODE_IS_MIN(n) (n->keys_num == MYBTREE_KEYS_NUM_MIN)

struct mybnode;
// 16k节点 只有叶子节点存数据索引 1022 <= keys <= 2045, 结构体大小：(2045 + 2046) * 4，还剩5*4个字节
struct mybnode {
    // 磁盘数据
    uint8_t leaf;
    uint16_t keys_num;
    uint32_t left_idx;
    uint32_t right_idx;
    int keys[MYBTREE_KEYS_NUM_MAX];
    union
    {
        int children_idxs[MYBTREE_CHILDS_NUM_MAX]; // 子节点在文件中的索引号
        int data_idxs[MYBTREE_KEYS_NUM_MAX]; // 数据在文件中的索引号
    };
    
    // 内存数据
    union {
        void *datas[MYBTREE_KEYS_NUM_MAX];
        struct mybnode *childrens[MYBTREE_CHILDS_NUM_MAX];
    };
    int node_idx;
    struct mybnode *left;
    struct mybnode *right;
} __attribute__((packed));
typedef struct mybnode mybnode;

typedef struct {
    // 磁盘数据
    int root_idx; // 根节点索引
    int keys_num; // key的数量
    int nodes_num; // 节点数量
    int threthod; // 除根节点 threthod -1 <= keys_num <= 2threthod - 1
    int node_size; // 节点大小，始终是16k
    uint8_t bitmap_idx_data[MYBTREE_BITMAP_SIZE/8]; // 用来分配节点索引号
    uint8_t bitmap_data_data[MYBTREE_BITMAP_SIZE/8]; // 用来分配数据索引号

    // 内存数据
    mybnode *root;
    char *name; // 文件名，不含后缀
    mybitmap bitmap_idx;
    mybitmap bitmap_data;
} __attribute__((packed)) mybtree;

typedef void (*mybtree_travel_handler)(mybtree *, mybnode *, int);

mybtree *mybtree_create(char *name);
void *mybtree_find(mybtree *t, int key);
void mybtree_insert(mybtree *t, int key, void *data);
void mybtree_delete(mybtree *t, int key);
int mybtree_flush_disk(mybtree *t);
void mybtree_travel(mybtree *t, mybnode *n, mybtree_travel_handler hander, int *);
